﻿#define _CRT_SECURE_NO_WARNINGS 1
//题目：最短距离
//有 N个村庄，编号 1到 N。
//村庄之间有 M条无向道路，第 i条道路连接村庄 ai和村庄 bi，长度是 ci。
//所有村庄都是连通的。
//共有 K个村庄有商店，第 j个有商店的村庄编号是 xj。
//然后给出 Q个询问，第 k个询问给出一个村庄的编号 yk，问该村庄距离最近的商店有多远？
//输入格式
//第一行包含两个整数 N, M。
//接下来 M行，每行包含三个整数 ai, bi, ci，表示第 i条道路连接村庄 ai和村庄 bi，长度是 ci。
//再一行包含整数 K。
//接下来 K行，每行包含一个整数 xj，表示第 j个有商店的村庄编号是 xj。
//再一行包含整数 Q。
//接下来 Q行，每行包含一个整数 yk，表示询问编号为 yk的村庄与其距离最近的商店之间的距离。
//输出格式
//对于每个询问，输出该询问的结果。
//数据范围
//2≤N≤105,N−1≤M≤min(N(N−1)2, 105),1≤Q≤105,1≤K≤N,1≤ci≤10000
//输入样例：
//7 7
//1 2 5
//1 4 3
//2 3 2
//2 5 1
//3 6 7
//5 6 8
//6 7 6
//3
//7
//5
//4
//7
//1
//2
//3
//4
//5
//6
//7
//输出样例：
//3
//1
//3
//0
//0
//6
//0
//这题对我来说最直接的理解方法就是要求从特定村庄到任意商店的最短距离。
//从这个角度看，我们用一个虚拟点将所有的商店连接在一起，且边长为0，
//此时求特定村庄到任意商店的最短距离就转变成了求特定村庄到该虚拟点的距离。
//换句话说，此时多源点多汇点最短路问题就转变成了多源点单汇点问题，
//如果我们将汇点视为源点而源点视为汇点，该问题就是一个典型的单源最短路问题，
//使用djs算法求解该虚拟点到所有村庄的距离所得到的dist[i]即该虚拟点到村庄i的最短距离，就是村庄i到任意商店的最短距离

//spfa做法
//#include<iostream>
//#include<algorithm>
//#include<queue>
//#include<vector>
//#include<cstring>
//using namespace std;
//const int N = 300010;//由于超级源点和是无向图，无向图需开两倍，k个商店超级源点需要连接k个
//int h[N], e[N], ne[N], w[N], idx;
//bool st[N];
//int n, m;
//int dist[N];
//
//void add(int a, int b, int c)
//{
//    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//void spfa()
//{
//    memset(dist, 0x3f, sizeof dist);
//    queue<int>q;
//    dist[0] = 0;
//    st[0] = true;
//    q.push(0);//从超级源点开始走
//    while (q.size())
//    {
//        int t = q.front();
//        q.pop();
//        st[t] = false;
//        for (int i = h[t]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (dist[j] > dist[t] + w[i])
//            {
//                dist[j] = dist[t] + w[i];
//                if (!st[j])
//                {
//                    st[j] = true;
//                    q.push(j);
//                }
//            }
//        }
//    }
//}
//int main()
//{
//    cin >> n >> m;
//    memset(h, -1, sizeof h);
//    for (int i = 0; i < m; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        //无向图
//        add(a, b, c);
//        add(b, a, c);
//    }
//    int k;
//    cin >> k;
//    while (k--)
//    {
//        int num;
//        cin >> num;
//        add(0, num, 0);//设超级源点为0节点，到某个有商店的村庄，有商店的村庄是距离为0
//    }
//    spfa();
//    int q;
//    cin >> q;
//    while (q--)
//    {
//        int num;
//        cin >> num;
//        cout << dist[num] << endl;
//    }
//    return 0;
//}

//dijkstra堆优化做法
//#include<iostream>
//#include<algorithm>
//#include<queue>
//#include<vector>
//#include<cstring>
//using namespace std;
//const int N = 300010;//由于超级源点和是无向图，无向图需开两倍，k个商店超级源点需要连接k个
//int h[N], e[N], ne[N], w[N], idx;
//bool st[N];
//int n, m;
//int dist[N];
//typedef pair<int, int>PII;
//
//void add(int a, int b, int c)
//{
//    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//void dijkstra()
//{
//    memset(dist, 0x3f, sizeof dist);
//    priority_queue<PII, vector<PII>, greater<PII>>heap;
//    dist[0] = 0;
//    heap.push({ 0,0 });//左距离，右节点
//    while (heap.size())
//    {
//        PII t = heap.top();
//        heap.pop();
//        int ver = t.second; int distance = t.first;
//        if (st[ver]) continue;
//        st[ver] = true;
//        for (int i = h[ver]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (dist[j] > dist[ver] + w[i])
//            {
//                //这里遍历过的点还需要遍历，直到找到最小距离
//                //不能用st【】数组判断
//                dist[j] = dist[ver] + w[i];
//                heap.push({ dist[j],j });
//            }
//        }
//    }
//}
//int main()
//{
//    cin >> n >> m;
//    memset(h, -1, sizeof h);
//    for (int i = 0; i < m; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        //无向图
//        add(a, b, c);
//        add(b, a, c);
//    }
//    int k;
//    cin >> k;
//    while (k--)
//    {
//        int num;
//        cin >> num;
//        add(0, num, 0);//设超级源点为0节点，到某个有商店的村庄，有商店的村庄是距离为0
//    }
//    dijkstra();
//    int q;
//    cin >> q;
//    while (q--)
//    {
//        int num;
//        cin >> num;
//        cout << dist[num] << endl;
//    }
//    return 0;
//}
